1. Field of the Invention
The present invention relates generally to the field of computing systems, and more particularly to range matching of addresses.
2. Description of Related Art
Networking companies are scrambling in a race to design and develop high performance network processing products for the terabit router market while reducing the cost to implement 10 giga-bits per second/OC192 and above optical carrier network interfaces. Terabit routers demand a higher throughput of data packets for examining an incoming packet, retrieves a next hop location, and transfers the packet to destination. To produce a faster response time in matching an incoming address, a technique called range matching has been used. For background information on range matching, the reader is referred to multirange and multidimensional range matching algorithm as presented in: xe2x80x9cHighSpeed Policy-Based Packet Forwarding Using Efficient Multi-Dimensional Range Matchingxe2x80x9d, Lakshman and Stiliadis, Bell Labs, 1998.
Accordingly, it is desirable to have a method and system for fast matching of an incoming address with addresses in a memory.
The invention provides a range matching circuit that determines if a field value is within the specified range of values, described as a top end boundary (xe2x80x9ctop edgexe2x80x9d) and a bottom end boundary (xe2x80x9cbottom edgexe2x80x9d). This analysis is done by partitioning the incoming address into fields. In one embodiment, a 16-bit incoming address is divided into quarterly fields, or four segments of 4-bit addresses, for comparison with four 4-bit segments of the 16-bit top edge and the four 4-bit segments of the 16-bit bottom edge. Each 4-bit segment can be analyzed independently in parallel in which a combined result is generated at the output.